Created at : 2024-05-06 12:06
2212

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;
    vector<int> SensorPositions(N);
    for(auto &SensorPosition : SensorPositions) cin >> SensorPosition;
    sort(SensorPositions.begin(), SensorPositions.end());

    vector<int> Ranges;
    for(int i = 1; i < SensorPositions.size(); ++i)
    {
        if(SensorPositions[i] == SensorPositions[i - 1]) continue;
        Ranges.push_back(SensorPositions[i] - SensorPositions[i - 1]);
    }
    sort(Ranges.begin(), Ranges.end());
    int Sum = 0;
    for(int i = 0; i < static_cast<int>(Ranges.size()) - K + 1; ++i) Sum += Ranges[i];
    cout << Sum;

    return 0;
}

정렬과 그리디 알고리즘을 혼합하는 문제다.

문제가 이런저런 말을 쓰고 있지만 핵심은 K개의 구간의 길이의 합이 가장 작게 하는 문제다.
예제 입력과 출력을 보면서 알아보자

• 예제 입력

6
2
1 6 9 3 6 7

• 예제 출력

5

센서가 구간으로 지정될 수 있는 수라고 생각할 수 있다. 구간은 연속된 수이기 때문에 센서의 위치를 정렬하면 1 3 6 6 7 9이 된다. 여기서 출력이 5가 나오는 이유는 K개(2개)의 구간이 아래와 같이 선정되었기 때문이다.

1. [1, 3]
2. [6, 9]
   3 - 1 = 2, 9 - 6 = 3이기 때문에 총 합 5가 정답이 된다.

문제 이해가 끝났으니 알고리즘 아이디어를 알아 보자면 인접한 센서가의 거리 가장 긴 구간을 K - 1개 만큼 빼주면 된다.
아래의 그림을 참고하자면 센서의 위치와 인접한 센서간의 거리, 그리고 집중국(구간)을 표현한다.
집중국이 2개인 경우, 연결된 구간중 빈 부분이 1군대 생기게 된다. K개의 집중국의 경우 K - 1개의 빈 공간이 생기게 되고 빈 공간의 길이를 최대화 할때, 구간들의 합이 최소화 될 수 있다.

유형

• 그리디 알고리즘
• 정렬